package dp;

import java.util.Arrays;

public class canPartition {
    public boolean canPartition(int[] nums) {
        //01背包问题
        //2  3 8 9
        //和肯定为偶数
        //是否存在一个子集，结果为sum/2
        //然后先排序，再通过二分，找到小于等于sum的index
        //然后构建sum的dp，
        if (nums.length==1) {
            return false;
        }
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if (sum%2!=0) {
            return false;
        }
        sum/=2;
        Arrays.sort(nums);
        if(nums[nums.length-1]>sum){
            return false;
        }
        boolean[][]dp = new boolean[nums.length][sum+1];
        dp[0][nums[0]]=true;
        for(int i=0;i<nums.length;i++){
            dp[i][0]=true;
        }
        
        for(int i=1;i<nums.length;i++){
            //会出现重复加的情况，比如limit是8，2为true，第二个数为2，那么内循环中，2，4，6，8都会变成true
            for(int j=1;j<=sum;j++){
                //可能重复
                //1 1 5 6
                //3 3 3 4 5
                if (j>=nums[i]) {
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
                }else{
                     dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[nums.length-1][sum];
    }
  
    public static void main(String[] args) {
        canPartition obj = new canPartition();
        // int []nums = new int[]{3};
        int []nums = new int[]{4,4,4,4,4,4,4,4,8,8,8,8,8,8,8,8,12,12,12,12,12,12,12,12,16,16,16,16,16,16,16,16,20,20,20,20,20,20,20,20,24,24,24,24,24,24,24,24,28,28,28,28,28,28,28,28,32,32,32,32,32,32,32,32,36,36,36,36,36,36,36,36,40,40,40,40,40,40,40,40,44,44,44,44,44,44,44,44,48,48,48,48,48,48,48,48,52,52,52,52,52,52,52,52,56,56,56,56,56,56,56,56,60,60,60,60,60,60,60,60,64,64,64,64,64,64,64,64,68,68,68,68,68,68,68,68,72,72,72,72,72,72,72,72,76,76,76,76,76,76,76,76,80,80,80,80,80,80,80,80,84,84,84,84,84,84,84,84,88,88,88,88,88,88,88,88,92,92,92,92,92,92,92,92,96,96,96,96,96,96,96,96,97,99};
        // int []nums = new int[]{6,8,16,16,16,18,20};
        // int []nums = new int[]{8,8,16,16};
        // int []nums = new int[]{2,2,3,5};
        // int []nums = new int[]{3,3,3,4,5};
        // int []nums = new int[]{1,1,1,3};
        // int []nums = new int[]{1,2,3,5};
        // int []nums = new int[]{1,5,11,5};
        System.out.println(obj.canPartition(nums));
    }
}
